package com.zjsru.oneDay202204;

import java.util.TreeMap;

/**
 * @Author: likew
 * @Date: 2022/4/1
 *
 * 二倍数对数组
 * 给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <=i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]”时，返回 true；否则，返回 false。
 *
 *
 * 输入：arr = [4,-2,2,-4]
 * 输出：true
 * 解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
 *
 * 输入：arr = [3,1,3,6]
 * 输出：false
 */
public class canReorderDoubled {
    public boolean canReorderDoubled(int[] arr) {
        TreeMap<Integer,Integer> valToCnt = gatValtoCnt(arr);
    
        for (int val:valToCnt.keySet()) {
            int doubleVal = val * 2;
            
            if(valToCnt.get(val) ==  0) continue;
            
            if(valToCnt.getOrDefault(doubleVal,0) < valToCnt.get(val)){
                return false;
            }
            valToCnt.put(doubleVal,valToCnt.get(doubleVal) - valToCnt.get(val));
        }
        return true;
    }
    
    private TreeMap<Integer, Integer> gatValtoCnt(int[] arr) {
        TreeMap<Integer,Integer> ans = new TreeMap<>( (o1,o2) -> {
            if (Math.abs(o1) == Math.abs(o2)){
                return o1 - o2;
            }
            return Math.abs(o1) - Math.abs(o2);
        });
        for (int a: arr) {
            ans.put(a,ans.getOrDefault(a,0)+ 1);
        }
        return ans;
    }
    
    public static void main(String[] args) {
        canReorderDoubled canReorderDoubled = new canReorderDoubled();
        int[] arr = new int[]{4,-2,2,-4};
        System.out.println(canReorderDoubled.canReorderDoubled(arr));
    }
}
